{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition String Into Minimum Beautiful Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumBeautifulSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将字符串分割为最少的美丽子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串&nbsp;<code>s</code>&nbsp;，你需要将字符串分割成一个或者多个&nbsp;<strong>子字符串</strong>&nbsp;&nbsp;，使每个子字符串都是 <strong>美丽</strong>&nbsp;的。</p>\n",
    "\n",
    "<p>如果一个字符串满足以下条件，我们称它是 <strong>美丽</strong>&nbsp;的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它不包含前导 0 。</li>\n",
    "\t<li>它是 <code>5</code>&nbsp;的幂的 <strong>二进制</strong>&nbsp;表示。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回分割后的子字符串的 <strong>最少</strong>&nbsp;数目。如果无法将字符串&nbsp;<code>s</code>&nbsp;分割成美丽子字符串，请你返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>子字符串是一个字符串中一段连续的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"1011\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们可以将输入字符串分成 [\"101\", \"1\"] 。\n",
    "- 字符串 \"101\" 不包含前导 0 ，且它是整数 5<sup>1</sup> = 5 的二进制表示。\n",
    "- 字符串 \"1\" 不包含前导 0 ，且它是整数 5<sup>0</sup> = 1 的二进制表示。\n",
    "最少可以将 s 分成 2 个美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"111\"\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>我们可以将输入字符串分成 [\"1\", \"1\", \"1\"] 。\n",
    "- 字符串 \"1\" 不包含前导 0 ，且它是整数 5<sup>0</sup> = 1 的二进制表示。\n",
    "最少可以将 s 分成 3 个美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"0\"\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法将给定字符串分成任何美丽子字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 15</code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;要么是&nbsp;<code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-string-into-minimum-beautiful-substrings](https://leetcode.cn/problems/partition-string-into-minimum-beautiful-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-string-into-minimum-beautiful-substrings](https://leetcode.cn/problems/partition-string-into-minimum-beautiful-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1011\"', '\"111\"', '\"0\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isFive(self,num):\n",
    "        while num%5==0:\n",
    "            num/=5\n",
    "        if num==1:return True\n",
    "        return False\n",
    "\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        a=[20]*(len(s)+1)\n",
    "        a[-1]=0\n",
    "        for i in reversed(range(len(s))):\n",
    "            #print(s[i])\n",
    "            if s[i]==\"1\":\n",
    "                for j in range(i+1,len(s)+1):\n",
    "                    if self.isFive(int(s[i:j],2)):\n",
    "                        a[i]=min(a[i],a[j]+1)\n",
    "\n",
    "        return a[0] if a[0]<20 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        if s[0] == '0':\n",
    "            return -1\n",
    "\n",
    "        # Define a set of beautiful binary strings\n",
    "        beautiful_strings = {\"1\", \"101\", \"11001\", \"1111101\", \"1001110001\", \"110000110101\", \"11110100001001\"}\n",
    "\n",
    "        n = len(s)\n",
    "        f = [float('inf')] * (n + 10)\n",
    "        f[0] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                current_substring = s[i:j+1]\n",
    "                if current_substring in beautiful_strings:\n",
    "                    f[j+1] = min(f[j+1], f[i] + 1)\n",
    "\n",
    "        if f[n] == float('inf'):\n",
    "            return -1\n",
    "\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5**i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [inf] * (n+1)\n",
    "        f[n] = 0\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i:i+len(t)] == t:\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        \n",
    "        ans = f[0]\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理5的次幂\n",
    "pow5 = set([bin(5 ** i)[2:] for i in range(7)])\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # 选或不选模板，类比131分割回文串\n",
    "        @cache\n",
    "        def f(i: int) -> int:  # 以i结尾的最少段数\n",
    "            if i == n:\n",
    "                return 0\n",
    "            # 求最少，初始为最大\n",
    "            res = inf\n",
    "            for j in range(i, n):\n",
    "                x = s[i:j + 1]\n",
    "                # 满足条件跳下一个点\n",
    "                if x[0] != 0 and x in pow5:\n",
    "                    res = min(res, f(j + 1) + 1)\n",
    "            return res\n",
    "\n",
    "        ans = f(0)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        f = [inf] * n + [0]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "\n",
    "            if s[i] == '0': continue\n",
    "\n",
    "            for t in pow5:\n",
    "\n",
    "                if i + len(t) > n:\n",
    "\n",
    "                    break\n",
    "\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "\n",
    "        return f[0] if f[0] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        if s == '':\n",
    "            return 0\n",
    "        for i in range(6,-1,-1):\n",
    "            if s.startswith(self.pow5[i]):\n",
    "                count = self.minimumBeautifulSubstrings(s[len(self.pow5[i]):])\n",
    "                if count == -1:\n",
    "                    continue\n",
    "                return 1 + count\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = set(bin(5 ** i)[2:] for i in range(20))\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, t: str) -> int:\n",
    "        n = len(t)\n",
    "        ans = [0] + [n + 5] * n\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i):\n",
    "                if t[j : i] in s:\n",
    "                    ans[i] = min(ans[i], ans[j] + 1)\n",
    "        return -1 if ans[-1] > n else ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos: int) -> int:\n",
    "            if pos == n:\n",
    "                return 0\n",
    "            if s[pos] == '0':\n",
    "                return inf\n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if pos + len(t) > n:\n",
    "                    break\n",
    "                if s[pos:pos + len(t)] == t:\n",
    "                    res = min(res, dfs(pos + len(t)) + 1)\n",
    "\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        samples = ['1', '101', '11001', '1111101', '1001110001', '110000110101', '11110100001001']\n",
    "        dp = [0] + [n+1] * n\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for sample in samples:\n",
    "                if s[i-1] == '0':\n",
    "                    break\n",
    "                if len(sample) > i:\n",
    "                    break\n",
    "                if sample == s[i - len(sample): i]:\n",
    "                    dp[i] = min(dp[i], dp[i-len(sample)] + 1)\n",
    "        print(dp)\n",
    "        return dp[-1] if dp[-1] < n+1 else -1\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        return f[0] if f[0] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5 **i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @cache\n",
    "        # 这里的索引i代表什么？处理到第几个字符\n",
    "        # dfs返回什么？表示从s[i]开始的后缀，最少要划分多少段？\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            ch = s[i]\n",
    "            if ch == \"0\":\n",
    "                return inf\n",
    "            # 初始化为1个大值\n",
    "            ans = inf\n",
    "            # 枚举什么？\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                # 如果[i, i + len(t)-1]和t相等，那么就有转移的机会\n",
    "                if s[i: i + len(t)] == t:\n",
    "                    ans = min(ans, dfs(i + len(t)) + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0)\n",
    "\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        cs = ['1', '101', '11001', '1111101', '1001110001', '110000110101', '11110100001001']\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == len(s):\n",
    "                return 0\n",
    "            \n",
    "            ret = inf\n",
    "            for c in cs[::-1]:\n",
    "                if s[i:i + len(c)] == c:\n",
    "                    ret = min(ret, 1 + dfs(i + len(c)))\n",
    "            return ret\n",
    "        \n",
    "        res = dfs(0)\n",
    "        if res == inf:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        all_str=['1']\n",
    "        n=len(s)\n",
    "        for i in range(2**14):\n",
    "            j=i\n",
    "            while j>5:\n",
    "                if j%5:\n",
    "                    break\n",
    "                j//=5\n",
    "            if j==5:\n",
    "                binary_i=''\n",
    "                while i:\n",
    "                    binary_i+=str(i%2)\n",
    "                    i//=2\n",
    "                all_str.append(binary_i[::-1])\n",
    "\n",
    "        ans=inf\n",
    "        @cache\n",
    "        def dfs(idx:int,total):\n",
    "            nonlocal ans\n",
    "            if idx==n:\n",
    "                ans=min(ans,total)\n",
    "                return\n",
    "            for binary_5 in all_str:\n",
    "                cur_len=len(binary_5)\n",
    "                if s[idx:idx+cur_len]==binary_5:\n",
    "                    dfs(idx+cur_len,total+1)\n",
    "        dfs(0,0)\n",
    "        return ans if ans<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "q = [bin(5 ** x)[2:] for x in range(8)]\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        def dfs(s_i, path):\n",
    "            if s_i == n:\n",
    "                res.append(path[:])\n",
    "            for i in range(s_i, n):\n",
    "                if s[s_i : i + 1] in q:\n",
    "                    path.append(s[s_i : i + 1])\n",
    "                    dfs(i + 1, path)\n",
    "                    path.pop()\n",
    "        dfs(0, [])\n",
    "        ans = inf\n",
    "        for x in res:\n",
    "            ans = min(ans, len(x))\n",
    "        return ans if ans != inf else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': \n",
    "                continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        return f[0] if f[0] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "st = set()\n",
    "for i in range(10):\n",
    "    st.add(bin(5 ** i)[2:])\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if s[:i] in st: return 1\n",
    "            res = inf\n",
    "            for j in range(i):\n",
    "                if s[j:i] in st:\n",
    "                    res = min(res, f(j) + 1)\n",
    "            return res\n",
    "        return f(n) if f(n) != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        ps=[]\n",
    "        i = 0\n",
    "        x=''\n",
    "        while True:\n",
    "            x = bin(5**i)[2:]\n",
    "            if len(x) > len(s):\n",
    "                break\n",
    "            ps.append(x)\n",
    "            i+=1\n",
    "        \n",
    "        n = len(s)\n",
    "        a = [-1]*(n+1)\n",
    "        a[0]=0\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1]=='1':\n",
    "                t = 1\n",
    "                for x in ps:\n",
    "                    if len(x)> i:break\n",
    "                    if s[i-len(x):i] == x:\n",
    "                        if  a[i-len(x)] != -1:\n",
    "                            if a[i]==-1: \n",
    "                                a[i]=a[i-len(x)]+1\n",
    "                            else :a[i] = min(a[i], a[i-len(x)]+1)\n",
    "        print(a)\n",
    "        return a[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        table = {1, 5, 25, 125, 625, 3125, 15625};\n",
    "        dp = [16] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            cur = 0\n",
    "            wei = 1\n",
    "            for j in range(i, -1, -1):\n",
    "                cur += wei * int(s[j])\n",
    "                wei <<= 1\n",
    "                if s[j] != '0' and cur in table:\n",
    "                    dp[i] = min(dp[i], dp[j - 1] + 1) if j else 1\n",
    "        return dp[-1] if dp[-1]<16 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        return f[0] if f[0] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        f = [inf] * n + [0]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "\n",
    "            if s[i] == '0': continue\n",
    "\n",
    "            for t in pow5:\n",
    "\n",
    "                if i + len(t) > n:\n",
    "\n",
    "                    break\n",
    "\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "\n",
    "        return f[0] if f[0] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "five = set()\n",
    "x = 1\n",
    "maxNum = 1 << 15\n",
    "while x < maxNum:\n",
    "    five.add(x)\n",
    "    x *= 5\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        def isFive(s):\n",
    "            if s[0] == \"0\":\n",
    "                return False\n",
    "            x = 0\n",
    "            n = len(s)\n",
    "            for i in range(n-1, -1, -1):\n",
    "                if s[i] == \"1\":\n",
    "                    x |= 1 << n-1-i\n",
    "    \n",
    "            return x in five   \n",
    "\n",
    "        n = len(s)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for j in range(n):\n",
    "            for i in range(j+1):\n",
    "                if isFive(s[i:j+1]):\n",
    "                    dp[j+1] = min(dp[j+1], dp[i] + 1)\n",
    "        if dp[-1] != inf:\n",
    "            return dp[-1]\n",
    "        return -1\n",
    "        \n",
    "                        \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5**i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        \n",
    "        # dfs(i)含义是划分从s[i]开始的后缀，最少需要多少项？\n",
    "        # dfs[n] = 0\n",
    "        # 求dfs[0]\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            # 0不能当前缀\n",
    "            if s[i] == '0':\n",
    "                return inf\n",
    "            ans = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i:i+len(t)] == t:\n",
    "                    ans = min(ans, dfs(i+len(t)) + 1)\n",
    "\n",
    "            return ans\n",
    "        ans = dfs(0)\n",
    "        \n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "                \n",
    "        return f[0] if f[0] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fv = set()\n",
    "x = 1\n",
    "for i in count(1):\n",
    "    fv.add(bin(x)[2:])\n",
    "    if x * 5 <= (1 << 16):\n",
    "        x *= 5\n",
    "    else:\n",
    "        break\n",
    "# print(fv)\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, cnt: int) -> None:\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans = min(ans, cnt)\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                x = s[i:j + 1]\n",
    "                if x[0] != 0 and x in fv:\n",
    "                    f(j + 1, cnt + 1)\n",
    "\n",
    "        ans = inf\n",
    "        f(0, 0)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        return f[0] if f[0] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        return f[0] if f[0] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5=[bin(5**i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i==n:\n",
    "                return 0\n",
    "            \n",
    "            if s[i] == \"0\":\n",
    "                return inf\n",
    "            res = inf\n",
    "\n",
    "            for t in pow5:\n",
    "                if i+len(t)>n:\n",
    "                    break\n",
    "                if s[i:i+len(t)] ==t:\n",
    "                   res = min(res,dfs(i+len(t))+1)\n",
    "            return res \n",
    "        ans = dfs(0)\n",
    "\n",
    "        return ans if ans<inf else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        if s.endswith('0'):\n",
    "            return -1\n",
    "        n, a, i = len(s), [], 1\n",
    "        while True:\n",
    "            x = bin(i)[2:]\n",
    "            if len(x) > n:\n",
    "                break\n",
    "            a.append(x)\n",
    "            i *= 5\n",
    "        a.reverse()\n",
    "        \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            m = inf\n",
    "            if s[i] != '1':\n",
    "                return m\n",
    "            for t in a:\n",
    "                if s.find(t, i) == i:\n",
    "                    m = min(m, 1 + f(i + len(t)))\n",
    "            return m\n",
    "            \n",
    "        x = f(0)\n",
    "        return x if x <= n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        # 1,101,11001,1111101,1001110001,110000110101,11110100001001\n",
    "        n=len(s);f=[1000]*(n+1);f[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            if(s[i-1]=='1'):f[i]=min(f[i],f[i-1]+1)\n",
    "            if(i>=3 and s[i-3:i]=='101'):f[i]=min(f[i],f[i-3]+1)\n",
    "            if(i>=5 and s[i-5:i]=='11001'):f[i]=min(f[i],f[i-5]+1)\n",
    "            if(i>=7 and s[i-7:i]=='1111101'):f[i]=min(f[i],f[i-7]+1)\n",
    "            if(i>=10 and s[i-10:i]=='1001110001'):f[i]=min(f[i],f[i-10]+1)\n",
    "            if(i>=12 and s[i-12:i]=='110000110101'):f[i]=min(f[i],f[i-12]+1)\n",
    "            if(i>=14 and s[i-14:i]=='11110100001001'):f[i]=min(f[i],f[i-14]+1)\n",
    "        if(f[n]==1000):return -1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n + [0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': continue\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        return f[0] if f[0] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x) :\n",
    "    res=\"\"\n",
    "    while x!=0 :\n",
    "        res+=str(x%2)\n",
    "        x//=2\n",
    "    return res[::-1]\n",
    "ans=[]\n",
    "for i in range(7) :\n",
    "    ans.append(f(pow(5,i)))\n",
    "print(ans)\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        #每部分为5的次方的二进制\n",
    "        #最多割len(s)-1\\U0001f52a\n",
    "        #最少0\\U0001f52a\n",
    "        n=len(s)\n",
    "        path=[]\n",
    "        def dfs(i,cnt) :\n",
    "            if i==n :\n",
    "                if len(path)==cnt :\n",
    "                    nonlocal ok\n",
    "                    ok=True\n",
    "                return\n",
    "            for j in range(i,n) :\n",
    "                t=s[i:j+1]\n",
    "                if t in ans :\n",
    "                    path.append(t)\n",
    "                    dfs(j+1,cnt,)\n",
    "                    path.pop()\n",
    "        for i in range(1,n+1) :\n",
    "            ok=False\n",
    "            dfs(0,i)\n",
    "            if ok :\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if s[i] == '0':\n",
    "                return inf\n",
    "            ans = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i:i+len(t)] == t:\n",
    "                    ans = min(ans, dfs(i + len(t)) + 1)\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import inf\n",
    "from functools import cache\n",
    "from typing import List\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @cache  # 使用缓存来避免重复计算\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n: \n",
    "                return 0\n",
    "            if s[i] == '0': \n",
    "                return inf  # 不能包含前导 0\n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    res = min(res, dfs(i + len(t)) + 1)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n: return 0\n",
    "            if s[i] == '0': return inf  # 不能包含前导 0\n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    res = min(res, dfs(i + len(t)) + 1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        f = [inf] * n + [0]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "\n",
    "            if s[i] == '0': continue\n",
    "\n",
    "            for t in pow5:\n",
    "\n",
    "                if i + len(t) > n:\n",
    "\n",
    "                    break\n",
    "\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "\n",
    "        return f[0] if f[0] < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "q = [bin(5 ** x)[2:] for x in range(8)]\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n: return 0\n",
    "            if s[i] == '0': return inf\n",
    "            ans = inf\n",
    "            for t in q:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i : i + len(t)] == t:\n",
    "                    ans = min(ans, dfs(i + len(t)) + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(0)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        all_str=['1']\n",
    "        n=len(s)\n",
    "        for i in range(2**14):\n",
    "            j=i\n",
    "            while j>5:\n",
    "                if j%5:\n",
    "                    break\n",
    "                j//=5\n",
    "            if j==5:\n",
    "                binary_i=''\n",
    "                while i:\n",
    "                    binary_i+=str(i%2)\n",
    "                    i//=2\n",
    "                all_str.append(binary_i[::-1])\n",
    "        print(all_str)\n",
    "        ans=inf\n",
    "        def dfs(idx:int,total):\n",
    "            nonlocal ans\n",
    "            if idx==n:\n",
    "                ans=min(ans,total)\n",
    "                return\n",
    "            for binary_5 in all_str:\n",
    "                cur_len=len(binary_5)\n",
    "                if s[idx:idx+cur_len]==binary_5:\n",
    "                    dfs(idx+cur_len,total+1)\n",
    "        dfs(0,0)\n",
    "        return ans if ans<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = set()\n",
    "for i in range(8):\n",
    "    m.add(5 ** i)\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        sub_s = []\n",
    "        ans = math.inf\n",
    "        if s == '1':\n",
    "            return 1\n",
    "        if s == '0':\n",
    "            return -1\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == len(s) - 1:\n",
    "                sub_s.append(s[-1])\n",
    "                tmp = list(''.join(sub_s).split(','))\n",
    "                flag = True\n",
    "                for n in tmp:\n",
    "                    if n[0] == '0':\n",
    "                        flag = False\n",
    "                        break\n",
    "                    n = int(n, 2)\n",
    "                    if n not in m:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    ans = min(ans, len(tmp))\n",
    "                sub_s.pop()\n",
    "                return\n",
    "            sub_s.append(s[i])\n",
    "            dfs(i + 1)\n",
    "            sub_s.append(',')\n",
    "            dfs(i + 1)\n",
    "            sub_s.pop()\n",
    "            sub_s.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        def check(x):\n",
    "            if x == 0:\n",
    "                return False\n",
    "            while x % 5 == 0:\n",
    "                x = x // 5\n",
    "            return x == 1\n",
    "        n = len(s)\n",
    "        dp = [float('inf')] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range (1, n + 1):\n",
    "            if s[i-1] == '0': continue\n",
    "            x = 0\n",
    "            for j in range(i, n+1):\n",
    "                x = (x << 1) + (ord(s[j-1]) - ord('0'))\n",
    "                if check(x): dp[j] = min(dp[j], dp[i-1] + 1)\n",
    "        return dp[-1] if dp[-1] < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5**i)[2:] for i in range(7)]\r\n",
    "class Solution:\r\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        res = float('inf')\r\n",
    "        @cache\r\n",
    "        def dfs(i):\r\n",
    "            nonlocal res\r\n",
    "            if i == n:\r\n",
    "                return 0\r\n",
    "            if s[i] == '0':\r\n",
    "                return float('inf')\r\n",
    "            for p in pow5:  \r\n",
    "                k = i + len(p)\r\n",
    "                if k > n:\r\n",
    "                    break\r\n",
    "                if s[i:k] == p:\r\n",
    "                    res = min(res, dfs(k) + 1)\r\n",
    "            return res\r\n",
    "        ans = dfs(0)\r\n",
    "        return ans if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5**i)[2:] for i in range(7)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        f = [inf] *(n+1)\n",
    "\n",
    "        f[n]= 0\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == '0':\n",
    "                continue\n",
    "            for t in pow5:\n",
    "                if i+len(t)>n:\n",
    "                    break\n",
    "\n",
    "                if s[i:i+len(t)] ==t :\n",
    "                    f[i] = min(f[i],f[i+len(t)]+1)\n",
    "\n",
    "        return f[0] if f[0]< inf else -1   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "visited = set()\n",
    "nums = set()\n",
    "cnt = 0\n",
    "while True:\n",
    "    new = bin(pow(5,cnt))[2:]\n",
    "    cnt += 1\n",
    "    if len(new) > 15:\n",
    "        break\n",
    "    visited.add(new)\n",
    "    nums.add(len(new))\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        #print(visited,nums)\n",
    "        res = inf\n",
    "        def dfs(l,stack):\n",
    "            nonlocal res\n",
    "            if l == n:\n",
    "                #print(stack)\n",
    "                res = min(res,len(stack))\n",
    "                return\n",
    "            for r in range(l,n):\n",
    "                if r-l+1 not in nums:\n",
    "                    continue\n",
    "                a = s[l:r+1]\n",
    "                if a not in visited:\n",
    "                    continue\n",
    "                stack.append(a)\n",
    "                dfs(r+1,stack)\n",
    "                stack.pop()\n",
    "        dfs(0,[])\n",
    "        return -1 if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        #print(int(\"1001110001101\",2))\n",
    "        pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "        print(pow5)\n",
    "        n=len(s)\n",
    "        ans=float(\"inf\")\n",
    "        def dfs(i,cnt):\n",
    "            nonlocal ans\n",
    "            if cnt>ans:\n",
    "                return \n",
    "            if i==n:\n",
    "                ans=min(ans,cnt)\n",
    "                return\n",
    "            if s[i]==\"0\":\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                #if s[j]==0:\n",
    "                    #continue\n",
    "       \n",
    "                if s[i:j+1] in pow5:\n",
    "\n",
    "                   # print(s[i:j+1])\n",
    "                    dfs(j+1,cnt+1)\n",
    "\n",
    "            return \n",
    "\n",
    "        dfs(0,0)\n",
    "        if ans==float(\"inf\"):\n",
    "            return -1\n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "five = set()\n",
    "x = 1\n",
    "maxNum = 1 << 15\n",
    "while x < maxNum:\n",
    "    five.add(x)\n",
    "    x *= 5\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:  \n",
    "\n",
    "        n = len(s)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for j in range(n):\n",
    "            k = 0\n",
    "            x = 0\n",
    "            for i in range(j,-1,-1):\n",
    "                if s[i] != \"0\":\n",
    "                    x |= 1 << k\n",
    "                    if x in five:\n",
    "                        dp[j+1] = min(dp[j+1], dp[i] + 1)\n",
    "                k += 1    \n",
    "        if dp[-1] != inf:\n",
    "            return dp[-1]\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = -1\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            # 一次有效的划分\n",
    "            if i == n:return 0\n",
    "            # 开头是'0'直接返回\n",
    "            if s[i] == '0':return inf\n",
    "            res = inf\n",
    "            # 枚举分割出来的字串\n",
    "            for j in pow5:\n",
    "                if i + len(j) > n:\n",
    "                    break\n",
    "                if s[i: i + len(j)] == j:\n",
    "                    res = min(res, dfs(i + len(j)) + 1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        def mi5(n):\n",
    "            while n % 5 == 0:\n",
    "                n //= 5\n",
    "            return n == 1\n",
    "        \n",
    "        m = len(s)\n",
    "        if s[0] == '0':\n",
    "            return -1\n",
    "        \n",
    "        ans = inf\n",
    "        def f(i, step):\n",
    "            if i >= m:\n",
    "                nonlocal ans\n",
    "                ans = min(ans, step)\n",
    "                return \n",
    "            if s[i] == '0':\n",
    "                return\n",
    "            cur = 0\n",
    "            for j in range(i, m):\n",
    "                cur = cur * 2 + int(s[j])\n",
    "                if mi5(cur):\n",
    "                    f(j+1, step + 1)\n",
    "        f(0,0)\n",
    "        return ans if ans != inf else -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        \n",
    "        f = dict()\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            nonlocal f\n",
    "\n",
    "            if i == n:\n",
    "                f[i] = 0\n",
    "                return\n",
    "\n",
    "            if s[i] == '0':\n",
    "                f[i] = inf\n",
    "                return \n",
    "\n",
    "            f[i] = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i:i+len(t)] == t:\n",
    "                    dfs(i + len(t))\n",
    "                    f[i] = min(f[i], f[i + len(t)] + 1)\n",
    "        dfs(0)\n",
    "\n",
    "        ans = f[0]\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            # 一次有效的划分\n",
    "            if i == n:return 0\n",
    "            # 开头是'0'直接返回\n",
    "            if s[i] == '0':return inf\n",
    "            res = inf\n",
    "            # 枚举分割出来的字串\n",
    "            for j in pow5:\n",
    "                if i + len(j) > n:\n",
    "                    break\n",
    "                if s[i: i + len(j)] == j:\n",
    "                    res = min(res, dfs(i + len(j)) + 1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n: return 0\n",
    "            if s[i] == '0': return inf  # 不能包含前导 0\n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    res = min(res, dfs(i + len(t)) + 1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pow5 = [bin(5**i)[2:] for i in range(7)]\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if s[i] == \"0\":\n",
    "                return inf \n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if s[i:i+len(t)] == t:\n",
    "                    res = min(res,dfs(i+len(t))+1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "five_pow_bins = set()\n",
    "for i in count(0):\n",
    "    pow_str = bin(5 ** i)\n",
    "    if len(pow_str) > 17:\n",
    "        break\n",
    "    five_pow_bins.add(pow_str[2:])\n",
    "    #print(five_pow_bins)\n",
    "    \n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(index:int) -> int:\n",
    "            if index == -1:\n",
    "                return 0\n",
    "            ret = inf\n",
    "            for i in range(0, index + 1):\n",
    "                if s[i:index + 1] in five_pow_bins:\n",
    "                    ret = min(dfs(i - 1) + 1, ret)\n",
    "            return ret\n",
    "        ans = dfs(len(s) - 1)\n",
    "        return ans if ans != inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        if s.endswith('0'):\n",
    "            return -1\n",
    "        n, a, i = len(s), [], 1\n",
    "        while True:\n",
    "            x = bin(i)[2:]\n",
    "            if len(x) > n:\n",
    "                break\n",
    "            a.append(x)\n",
    "            i *= 5\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            m = inf\n",
    "            if s[i] != '1':\n",
    "                return m\n",
    "            for t in a:\n",
    "                if s.find(t, i) == i:\n",
    "                    m = min(m, 1 + f(i + len(t)))\n",
    "            return m\n",
    "            \n",
    "        x = f(0)\n",
    "        return x if x <= n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "bin_five = set()\n",
    "for i in range(7):\n",
    "    bin_five.add(bin(5**i)[2:])\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        # 先打表找出5的幂的二进制表示，且长度在15位以内\n",
    "        ans = inf \n",
    "        # 然后记忆化搜索，递归出口为\n",
    "        memo = collections.defaultdict(lambda : inf)\n",
    "        memo[\"\"] = 0\n",
    "        for val in bin_five:\n",
    "            memo[val] = 1\n",
    "        def dfs(val):\n",
    "            if val in memo:\n",
    "                return memo[val]\n",
    "            cost = inf\n",
    "            for i in range(1,len(val)):\n",
    "                if val[i:] in bin_five:\n",
    "                    cost = min(cost, dfs(val[:i]) + 1)\n",
    "            memo[val] = cost \n",
    "            return cost \n",
    "        \n",
    "        ans = dfs(s)\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n: return 0\n",
    "            if s[i] == '0': return inf  # 不能包含前导 0\n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    res = min(res, dfs(i + len(t)) + 1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "       n = len(s)\n",
    "\n",
    "       def check(x: int) -> bool:\n",
    "          while x != 1:\n",
    "             if x % 5:\n",
    "                return False\n",
    "             x //= 5\n",
    "          return True\n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i == n:\n",
    "             return 0\n",
    "          if s[i] == '0':\n",
    "             return inf\n",
    "          res = inf\n",
    "          sum = 0\n",
    "          for j in range(i, n):\n",
    "             sum = (sum << 1) | int(s[j])\n",
    "             if check(sum):\n",
    "                res = min(res, dfs(j + 1) + 1)\n",
    "          return res\n",
    "       res = dfs(0)\n",
    "       return res if res < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "g = [bin(5**i)[2:] for i in range(7)]\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            # 表示从i开始分割需要的最少数目\n",
    "            if i == n:return 0\n",
    "            if s[i] == '0':return inf\n",
    "            res = inf\n",
    "            for cur in g:\n",
    "                if len(cur)+i > n:\n",
    "                    break\n",
    "                if s[i:len(cur)+i] == cur:\n",
    "                    res = min(res,dfs(len(cur)+i)+1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理 2**15 以内的 5 的幂\n",
    "pow5 = [bin(5 ** i)[2:] for i in range(7)]\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n: return 0\n",
    "            if s[i] == '0': return inf  # 不能包含前导 0\n",
    "            res = inf\n",
    "            for t in pow5:\n",
    "                if i + len(t) > n:\n",
    "                    break\n",
    "                if s[i: i + len(t)] == t:  # 忽略切片的时间，这里的比较视作均摊 O(1)\n",
    "                    res = min(res, dfs(i + len(t)) + 1)\n",
    "            return res\n",
    "        ans = dfs(0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s: str) -> int:\n",
    "        ss=set()\n",
    "        for i in range(10):\n",
    "            ss.add(bin(5**i)[2:])\n",
    "        def dfs(t):\n",
    "            ans=inf\n",
    "            if s[:t] in ss:\n",
    "                return 1\n",
    "            for i in range(1,t):\n",
    "                if s[i:t] in ss:\n",
    "                    ans=min(ans,dfs(i)+1)\n",
    "            return ans \n",
    "        res=dfs(len(s))\n",
    "        return res if res<inf else -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumBeautifulSubstrings(self, s):\n",
    "        ans = 0\n",
    "        pow5 = [bin(5 ** i)[2:] for i in range(7)] # 记忆：获得一个数对应的二进制字符串的方法\n",
    "        cache = [-1] * len(s) # 记忆搜索：手动增加一个缓存，防止搜索时的重复计算\n",
    "        \n",
    "        def helper(i): # 获得以第i个字符结尾的最小分割数\n",
    "            if i < 0: return 0\n",
    "            res = math.inf\n",
    "            for p5 in pow5:\n",
    "                if i-len(p5) + 1 < 0: break\n",
    "                if s[i-len(p5)+1:i+1] == p5:\n",
    "                    if cache[i-len(p5)] == -1:\n",
    "                        res = min(res, helper(i-len(p5)) + 1)\n",
    "                    else:\n",
    "                        res = min(res, cache[i-len(p5)] + 1) \n",
    "            cache[i] = res\n",
    "            return res\n",
    "        ans = helper(len(s)-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
